package visitors;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import nodes.*;
import nodes.body.*;
import nodes.declarations.*;
import nodes.exprnodes.*;
import nodes.exprnodes.bin.*;
import nodes.exprnodes.consts.*;
import nodes.exprnodes.sequences.*;
import nodes.exprnodes.unary.*;
import nodes.exprnodes.variables.*;
import nodes.statements.*;
import nodes.statements.controlflow.*;
import table.*;

public class TypeAndScopeVisitor implements Visitor
{
    private boolean local;
    private SymbolTable table;

    public TypeAndScopeVisitor(SymbolTable table)
    {
        this.table = table;
        local = false;
    }

    /**
     * Visits BoolNode.
     *
     * @param n
     * @return Type.BOOL
     */
    public Type visit(BoolNode n)
    {
        return Type.BOOL;
    }

    /**
     * Visits CharNode.
     *
     * @param n
     * @return Type.CHAR
     */
    public Type visit(CharNode n)
    {
        return Type.CHAR;
    }

    /**
     * Visits FloatNode.
     *
     * @param n
     * @return Type.FLOAT
     */
    public Type visit(FloatNode n)
    {
        return Type.FLOAT;
    }

    /**
     * Visits IntNode.
     *
     * @param n
     * @return Type.INT
     */
    public Type visit(IntNode n)
    {
        return Type.INT;
    }

    /**
     * Visits StringNode.
     *
     * @param n
     * @return Type.STR
     */
    public Type visit(StringNode n)
    {
        return Type.STR;
    }

    /**
     * Visits ListNode.
     * 
     * If list is empty, returns LIST.
     * Otherwise:
     * <ul>
     *  <li>Collects type of its elements.</li>
     *  <li>Tries to find an element that is UNDEF</li>
     *  <li>If all elements are UNDEF, returns LIST</li>
     *  <li>Otherwise, continues iterating 
     *      through elements, comparing types of elements 
     *      to the element found previously</li>
     *  <li>If types of all the elements
     *      are equal to the type of the element, returns LIST</li>
     *  <li>Otherwise returns UNDEF</li>
     * </ul>
     *
     * @param n
     * @return 
     */
    public Object visit(ListNode n)
    {
        List<Type> elements = visitExprList(n.list);
        if (elements.size() == 0)
            return Type.LIST;
        
        // Try to find an element that is not UNDEF
        Type comparator = null;
        Iterator<Type> iterator = elements.iterator();
        while (iterator.hasNext())
        {
            Type e = iterator.next();
            if (!Type.isUndef(e))
            {
                comparator = e;
                break;
            }
        }
        // If all types are UNDEF, return LIST
        if (comparator == null)
            return Type.LIST;
        while (iterator.hasNext())
        {
            Type cur = iterator.next();
            // If types don't match, complain and return UNDEF
            if (cur != comparator && !Type.isUndef(cur))
            {
                ErrorHandler.complain("Lists can only store elements of the same type");
                return Type.UNDEF;
            }
        }
        return Type.LIST;
    }

    /**
     * Visits TupleNode.
     *
     * If tuple is empty, returns TUPLE.
     * Otherwise:
     * <ul>
     *  <li>Collects type of its elements.</li>
     *  <li>Returns TUPLE</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Object visit(TupleNode n)
    {
        if (n.list != null)
        {
            visitExprList(n.list);
        }
        return Type.TUPLE;
    }

    /*
     *
     * Arythmetic Operations
     *
     */

    /**
     * Visits PlusNode.
     *
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF, but</li>
     *  <ul>
     *      <li>If one child is not UNDEF and this child is not a number, complains</li>
     *  </ul>
     *  <li>If either child is not a number, returns UNDEF</li>
     *  <li>If either child is FLOAT, returns FLOAT.</li>
     *  <li>Otherwise returns INT</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(PlusNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isNumber(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isNumber(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only add integers and floats");
            }
            return Type.UNDEF;
        }
        if (!Type.isNumber(leftType) || !Type.isNumber(rightType))
        {
            ErrorHandler.complain("You can only add integers and floats");
            return Type.UNDEF;
        }
        if (leftType==Type.FLOAT || rightType==Type.FLOAT)
            return Type.FLOAT;
        return Type.INT;
    }

    /**
     * Visits MinusNode.
     *
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF.</li>
     *  <li>If either child is not a number, returns UNDEF</li>
     *  <li>If either child is FLOAT, returns FLOAT.</li>
     *  <li>Otherwise returns INT</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(MinusNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isNumber(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isNumber(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only minus integers and floats");
            }
            return Type.UNDEF;
        }
        if (!Type.isNumber(leftType) || !Type.isNumber(rightType))
        {
            ErrorHandler.complain("You can only minus integers and floats");
            return Type.UNDEF;
        }
        if (leftType==Type.FLOAT || rightType==Type.FLOAT)
            return Type.FLOAT;
        return Type.INT;
    }

    /**
     * Visits TimesNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF.</li>
     *  <li>If either child is not a number, returns UNDEF</li>
     *  <li>If either child is FLOAT, returns FLOAT.</li>
     *  <li>Otherwise returns INT</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(TimesNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isNumber(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isNumber(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only times integers and floats");
            }
            return Type.UNDEF;
        }
        if (!Type.isNumber(leftType) || !Type.isNumber(rightType))
        {
            ErrorHandler.complain("You can only times integers and floats");
            return Type.UNDEF;
        }
        if (leftType==Type.FLOAT || rightType==Type.FLOAT)
            return Type.FLOAT;
        return Type.INT;
    }

    /**
     * Visits DivideNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF.</li>
     *  <li>If either child is not a number, returns UNDEF</li>
     *  <li>If either child is FLOAT, returns FLOAT.</li>
     *  <li>Otherwise returns INT</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Object visit(DivideNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isNumber(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isNumber(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only divide integers and floats");
            }
            return Type.UNDEF;
        }
        if (!Type.isNumber(leftType) || !Type.isNumber(rightType))
        {
            ErrorHandler.complain("You can only divide integers and floats");
            return Type.UNDEF;
        }
        if (leftType==Type.FLOAT || rightType==Type.FLOAT)
            return Type.FLOAT;
        return Type.INT;
    }

    /**
     * Visits PowerNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF.</li>
     *  <li>If either child is not a number, returns UNDEF</li>
     *  <li>If either child is FLOAT, returns FLOAT.</li>
     *  <li>Otherwise returns INT</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(PowerNode n)
    {
        Type leftType = (Type)n.left.accept(this);
        Type rightType = (Type)n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isNumber(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isNumber(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only raise number to the power of number.");
            }
            return Type.UNDEF;
        }
        if (!Type.isNumber(leftType) || !Type.isNumber(rightType))
        {
            ErrorHandler.complain("You can only raise number to the power of number.");
            return Type.UNDEF;
        }
        if (leftType == Type.FLOAT || rightType == Type.FLOAT)
        {
            return Type.FLOAT;
        }
        return Type.INT;
    }

    /*
     *
     * Comparison Nodes: all the nodes are visited internally by
     * a private helper method visitComparisonNode().
     * 
     *
     */

    /**
     * Private helper method.
     * 
     * <em>Use only with comparison nodes.</em>
     * <ul>
     *  <li>If either child is UNDEF, returns UNDEF.</li>
     *  <li>If either child is not of basic type, complains and returns UNDEF</li>
     *  <li>If types of children don't match and an int 
     *      is not being compared to a float,
     *      complains and returns UNDEF </li>
     *  <li>Otherwise returns BOOL</li>
     * </ul>
     *
     * @param n
     * @return
     */
    private Type visitComparisonNode(BinExprNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isBasic(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isBasic(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You can only compare basic types");
            }
            return Type.UNDEF;
        }
        if (!Type.isBasic(leftType) || !Type.isBasic(rightType))
        {
            ErrorHandler.complain("You can only compare basic types");
            return Type.UNDEF;
        }
        if (leftType != rightType && !((leftType==Type.FLOAT && rightType==Type.INT)|| leftType==Type.INT && rightType==Type.FLOAT))
        {
            ErrorHandler.complain("You can only compare same types");
            return Type.UNDEF;
        }
        return Type.BOOL;
    }

    /**
     * Visits GreaterNode.
     * 
     * @param n
     * @return
     */
    public Type visit(GreaterNode n)
    {
        return visitComparisonNode(n);
    }

    /**
     * Visits GreaterOrEqualNode.
     *
     * @param n
     * @return
     */
    public Type visit(GreaterOrEqualNode n)
    {
        return visitComparisonNode(n);
    }

    /**
     * Visits LessNode.
     *
     * @param n
     * @return
     */
    public Type visit(LessNode n)
    {
        return visitComparisonNode(n);
    }

    /**
     * Visits LessOrEqualNode.
     *
     * @param n
     * @return
     */
    public Type visit(LessOrEqualNode n)
    {
        return visitComparisonNode(n);
    }

    /**
     * Visits EqualNode.
     *
     * @param n
     * @return
     */
    public Type visit(EqualNode n)
    {
        return visitComparisonNode(n);
    }

    /**
     * Visits NotEqualNode.
     *
     * @param n
     * @return
     */
    public Type visit(NotEqualNode n)
    {
        return visitComparisonNode(n);
    }

    /*
     * Boolean operator nodes
     *
     */

    /**
     * Visits AndNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, return UNDEF.</li>
     *  <li>If both children are of type BOOL, return BOOL</li>
     *  <li>Otherwise return UNDEF.</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Object visit(AndNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isBoolean(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isBoolean(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You cannot AND nonboolean values");
            }
            return Type.UNDEF;
        }
        if (Type.isBoolean(leftType) && Type.isBoolean(rightType))
            return Type.BOOL;
        ErrorHandler.complain("You cannot AND nonboolean values");
        return Type.UNDEF;
    }

    /**
     * Visits OrNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, return UNDEF.</li>
     *  <li>If both children are of type BOOL, return BOOL</li>
     *  <li>Otherwise return UNDEF.</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(OrNode n)
    {
        Type leftType = (Type)n.left.accept(this);
        Type rightType = (Type)n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
        {
            if ((!Type.isBoolean(leftType) && !Type.isUndef(leftType)) ||
                (!Type.isBoolean(rightType) && !Type.isUndef(rightType)))
            {
                ErrorHandler.complain("You cannot OR nonboolean values");
            }
            return Type.UNDEF;
        }
        if (leftType == Type.BOOL && rightType == Type.BOOL) return Type.BOOL;
        else ErrorHandler.complain("You cannot OR nonboolean values");
        return Type.UNDEF;
    }

    /**
     * Visits NotNode.
     *
     * <ul>
     *  <li>If child is UNDEF, return UNDEF.</li>
     *  <li>If child is of type BOOL, return BOOL</li>
     *  <li>Otherwise return UNDEF.</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(NotNode n)
    {
        Type t = (Type) n.expr.accept(this);
        if (t == Type.UNDEF) return Type.UNDEF;
        if (t != Type.BOOL)
        {
            ErrorHandler.complain("You cannot NOT a nonboolean value");
            return Type.UNDEF;
        }
        return Type.BOOL;
    }

    /*
     * Sequence operator nodes
     *
     */

    /**
     * Visits InNode.
     *
     * @param n
     * @return
     */
    public Type visit(InNode n)
    {
        Type t1 = (Type) n.left.accept(this);
        Type t2 = (Type) n.right.accept(this);
        if (t1 == Type.UNDEF || t2 == Type.UNDEF) return Type.UNDEF;
        if (!Type.isSequence(t2))
        {
            ErrorHandler.complain("You can only use 'in' with sequences.");
            return Type.UNDEF;
        }
        return Type.BOOL;
    }

    /**
     * Visits NotInNode.
     *
     * <ul>
     *  <li>If either child is UNDEF, return UNDEF.</li>
     *  <li>If right child is not a sequence type complain and return UNDEF.</li>
     *  <li>Otherwise return BOOL.</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(NotInNode n)
    {
        Type t1 = (Type) n.left.accept(this);
        Type t2 = (Type) n.right.accept(this);
        if (t1 == Type.UNDEF || t2 == Type.UNDEF)
            return Type.UNDEF;
        if (!Type.isSequence(t2))
        {
            ErrorHandler.complain("You can only use 'not in' with sequences.");
            return Type.UNDEF;
        }
        return Type.BOOL;
    }

    /**
     * Visits ConcatNode.
     * 
     * <ul>
     *  <li>If either child is UNDEF, return UNDEF.</li>
     *  <li>If both children are of type sequence,
     *  and of the same type, return their type.</li>
     *  <li>Otherwise return UNDEF.</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Object visit(ConcatNode n)
    {
        Type leftType = (Type) n.left.accept(this);
        Type rightType = (Type) n.right.accept(this);
        if (Type.isUndef(leftType) || Type.isUndef(rightType))
            return Type.UNDEF;
        if (Type.isSequence(leftType) &&
            leftType==rightType)
            return leftType;
        ErrorHandler.complain("You can only concatenate two sequences of the same type");
        return Type.UNDEF;
    }

    /**
     * Visits LenNode.
     *
     * <ul>
     *  <li>If child is UNDEF, return UNDEF.</li>
     *  <li>If child is not a sequence type complain and return UNDEF.</li>
     *  <li>Otherwise return INT.</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(LenNode n)
    {
        Type t = (Type)n.expr.accept(this);
        if (t == Type.UNDEF) return t;
        if (!Type.isSequence(t))
        {
            ErrorHandler.complain("You cannot discover the length of a non sequence");
            return Type.UNDEF;
        }
        return Type.INT;
    }

    /*
     * Variable Nodes
     *
     */

    /**
     * Visits VariableListNode.
     * 
     * <ul>
     *  <li>If the list has only one element, returns the type of that element.</li>
     *  <li>Otherwise:</li>
     *  <ul>
     *      <li>If the type of the left child is a basic type complain and return UNDEF</li>
     *      <li>Visit the right child.</li>
     *      <li>Restore the scope (just in case VariableNode changed it).</li>
     *      <li>Return the type of the right child.</li>
     *  </ul>
     * </ul>
     * 
     * @param n
     * @return The type of the variable deepest in the chain
     */
    public Type visit(VariableListNode n)
    {
        SymbolTable oldTable = table;
        Type type = (Type) n.left.accept(this);
        if (Type.isUndef(type))
        {
            table = oldTable;
            return Type.UNDEF;
        }
        if (n.right != null)
        {
            if (Type.isBasic(type))
            {
                ErrorHandler.complain("Basic types do not have internal fields.");
                table = oldTable;
                return Type.UNDEF;
            }
            
            local = true;
            type = (Type) n.right.accept(this);
            local = false;
        }
        table = oldTable;
        return type;
    }

    /**
     * Visits IndexNode.
     * 
     * <ul>
     *  <li>Check type of expression</li>
     *  <li>Lookup variable</li>
     *  <li>If it doesn't exists, complain and check type of indexing expression, return UNDEF</li>
     *  <li>If it is a sequence</li>
     *  <ul>
     *      <li>If type of indexing expression is not INT, complain and return UNDEF</li>
     *      <li>If type of variable is STR, return CHAR</li>
     *  </ul>
     *  <li>If indexing expression is not INT, complain</li>
     *  <li>Complain that you can only index sequences, return UNDEF</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(IndexNode n)
    {
        Type exprType = (Type) n.expr.accept(this);
        VariableDeclaration decl = table.lookupVariableDeclaration(n.id);
        if (decl == null)
        {
            if (local)
                ErrorHandler.complain("Variable " + n.id + " does not exist in " + table.node.getClass());
            if (!Type.isUndef(exprType) && exprType!=Type.INT)
            {
                if (local)
                    ErrorHandler.complain("You can only index with integers");
            }
            return Type.UNDEF;
        }
        if (Type.isSequence(decl.getType()))
        {
            if (!Type.isUndef(exprType) && exprType!=Type.INT)
            {
                if (local)
                    ErrorHandler.complain("You can only index with integers");
                return Type.UNDEF;
            }
            if (decl.getType()== Type.STR)
                return Type.CHAR;
            return Type.UNDEF;
        }
        if (!Type.isUndef(exprType) && exprType!=Type.INT)
        {
            if (local)
                ErrorHandler.complain("You can only index with integers");
        }
        ErrorHandler.complain("You can only index sequences");
        return Type.UNDEF;
    } 

    /**
     * Visits IdNode.
     *
     * <ul>
     *  <li>Lookup the variable in the right scope</li>
     *  <li>If does not exist, complain and return UNDEF</li>
     *  <li>If variable is of basic type, return this type</li>
     *  <li>Lookup the data type</li>
     *  <li>If it exists, change the scope and return the type</li>
     *  <li>If it doesn't exist, return UNDEF (Do not complain:
     *      if it's type was not defined, it was already complained)</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(IdNode n)
    {
        VariableDeclaration varDecl = table.lookupVariableDeclaration(n.id);
        if (varDecl == null)
        {
            if (local)
            {
                if (table.node.getClass() == DataDeclarationNode.class)
                {
                    ErrorHandler.complain("Field '" + n.id + "' does not exist in data declaration: '" + ((DataDeclarationNode) table.node).name + '\'');
                }
            }
            return Type.UNDEF;
        }
        if (Type.isBasic(varDecl.getType()))
            return varDecl.getType();
        DataDeclaration dataDecl = table.lookupDataDeclaration(varDecl.getType().getType());
        if (dataDecl!=null)
        {
            table = dataDecl.getScope();
            return varDecl.getType();
        }
        return Type.UNDEF;
    }

    /**
     * Visits nodes.exprnodes.unary.FuncCallNode
     *
     * @param n
     * @return
     */
    public Type visit(nodes.exprnodes.FuncCallNode n)
    {
        List<Type> params = visitExprList(n.params);
        FunctionDeclaration fdef = table.lookupFunctionDeclaration(n.id, params);
        if (fdef == null)
        {
            ErrorHandler.complain("Unknown function " + n.id + "(" + params.toString() + ")");
            return Type.UNDEF;
        }
        return fdef.getReturnType();
    }

    /*
     * Declarations
     *
     */
    
    /**
     * Visits BasicDeclarationNode.
     * 
       <ul>
     *  <li>If initialization expression is null, returns null</li>
     *  <li>Gets type of initialization expression</li>
     *  <li>If initialization expression is UNDEF, return</li>
     *  <li>If initialization expression is of different type that variable
     *      type and you're not assigning INT to FLOAT, complain
     *  </li>
     * </ul>
     *
     * @param n
     * @return null
     */
    public Type visit(BasicDeclarationNode n)
    {
        Type varType = n.type;
        if (n.init == null)
            return null;
        Type initType = (Type) n.init.accept(this);
        if (Type.isUndef(initType))
            return null;
        if (varType != initType && !(varType == Type.FLOAT && initType == Type.INT))
        {
            ErrorHandler.complain("You cannot assign a(n) " + initType + " to a " + varType);
        }
        return null;
    }

    /**
     * Visits UserDeclarationNode.
     *
     * <ul>
     *  <li>Collects initialization expressions types</li>
     *  <li>Does a lookup of the data type</li>
     *  <li>If the data type was not declared, complains and returns</li>
     *  <li>If initialization expression is empty, returns</li>
     *  <li>If number of initialization parameters is different than declared, complains</li>
     *  <li>Iterates through the initialization parameters</li>
     *  <li>If type of initialization parameter is different than declared,
     *      and type of initialization parameter is not UNDEF, complains
     *  </li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Object visit(UserDeclarationNode n)
    {
        Type varType = n.type;
        List<Type> init = visitExprList(n.init);
        DataDeclaration decl = table.lookupDataDeclaration(varType.getType());
        if (decl == null)
        {
            ErrorHandler.complain("Undeclared type: " + varType.getType());
            return null;
        }
        if (init.size() == 0)
            return null;
        if (decl.getFields().size() != init.size())
        {
            ErrorHandler.complain("Wrong number of initialization expressions");
        }
        for (int i = 0; i<init.size(); i++)
        {
            if (init.get(i) != decl.getFields().get(i) && !Type.isUndef(init.get(i)))
                ErrorHandler.complain("Wrong type of " + (i+1) + " field");
        }
        return null;
    }

    /**
     * Visits DataDeclarationNode but does nothing:
     * all checks were already done.
     *
     * @param n
     * @return
     */
    public Type visit(DataDeclarationNode n)
    {
        return null;
    }

    /**
     * Visits FieldNode.
     *
     * @param n
     * @return Type of the field.
     */
    public Type visit(FieldNode n)
    {
        return n.type;
    }

    /**
     * Visits FunctionDeclarationNode.
     *
     * <ul>
     *  <li>Changes scope to the scope of this function</li>
     *  <li>Restores back the scope</li>
     *  <li>If declared type is UNDEF, do not complain (Syntax error already reported)</li>
     *  <li>If declared type is void but return expression
     *      is not null, complains</li>
     *  <li>If declared type is not void, but return
     *      expression is null, complains</li>
     *  <li>If return type is not basic, look it up</li>
     *  <ul>
     *      <li>If type not found, complain and return</li>
     *  </ul>
     *  <li>If return expression is not UNDEF and declared return_type 
     *      is not void and return expression is of different type
     *      than declared, complains</li>
     * </ul>
     *
     * @param n
     * @return
     *
     */
    public Type visit(FunctionDeclarationNode n)
    {
        table = table.enterScope(n);
        n.body.accept(this);
        table = table.exitScope();
        if (Type.isUndef(n.return_type))
            return null;
        if (Type.isVoid(n.return_type))
        {
            if (n.body.returnExpr!=null)
                ErrorHandler.complain("Function '" + n.id + "': declared type was 'void', but return expression is not empty");
        }
        else
        {
            if (n.body.returnExpr == null)
            {
                ErrorHandler.complain("Function '" + n.id + "': declared type was '" + n.return_type.getType() + "', but return expression is empty");
            }
            else
            {
                if (!Type.isBasic(n.return_type))
                {
                    DataDeclaration dd = table.lookupDataDeclaration(n.return_type.getType());
                    if (dd == null)
                    {
                        ErrorHandler.complain("Function '" + n.id + "': unknown return type");
                    }
                }
                Type return_type = (Type) n.body.returnExpr.accept(this);
                if (!Type.isUndef(return_type) && return_type!=n.return_type)
                {
                    ErrorHandler.complain("Function '" + n.id + "': declared type was '" + n.return_type.getType() + "' but return expression is of type '" + return_type.getType() + '\'');
                }
            }
        }
        return null;
    }

    /**
     * Visits ProgramNode.
     * 
     * <ul>
     *  <li>Visits declarations, if present</li>
     *  <li>Enters scope of the main and visits it</li>
     *  <li>Restores the scope</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(ProgramNode n)
    {
        if (n.decl!=null)
        {
            n.decl.accept(this);
        }
        table = table.enterScope(n.body);
        n.body.accept(this);
        table = table.exitScope();
        return null;
    }

    public Type visit(nodes.statements.FuncCallNode n)
    {
        List<Type> params = visitExprList(n.params);
        FunctionDeclaration fdef = table.lookupFunctionDeclaration(n.id, params);
        if (fdef == null)
        {
            ErrorHandler.complain("Unknown function " + n.id + "(" + params.toString() + ")");
            return Type.UNDEF;
        }
        return Type.UNDEF;
    }

    /**
     * Visits FunctionBodyNode.
     * 
     * <ul>
     *  <li>Visits declarations, if present</li>
     *  <li>Visits statements, if present</li>
     *  <li>Visits return expression, if present</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(FunctionBodyNode n)
    {
        if (n.decl != null)
        {
            n.decl.accept(this);
        }
        if (n.stm != null)
        {
            n.stm.accept(this);
        }
        if (n.returnExpr != null)
        {
            n.returnExpr.accept(this);
        }
        return null;
    }

    /*
     * Control Statements
     *
     */

    /**
     * Visits IfNode.
     * 
     * <ul>
     *  <li>Visit condition expression</li>
     *  <li>If condition expression is not BOOL, complain</li>
     *  <li>Enter scope of if body, visit if body</li>
     *  <li>Restore scope</li>
     *  <li>Enter scope of else body, visit else body</li>
     *  <li>Restore scope</li>
     *  <li>Return null</li>
     * </ul>
     *
     * @param n
     * @return
     */
    public Type visit(IfNode n)
    {
        Type expr = (Type) n.expr.accept(this);
        if (!Type.isBoolean(expr) && !Type.isUndef(expr))
        {
            ErrorHandler.complain("Expression in if statement must evaluate to boolean");
        }
        table = table.enterScope(n.body);
        n.body.accept(this);
        table = table.exitScope();
        table = table.enterScope(n.elseBody);
        n.elseBody.accept(this);
        table = table.exitScope();
        return null;
    }

    /**
     * Visits RepeatNode
     * 
     * <ul>
     *  <li>Enter scope of repeat body, visit repeat body</li>
     *  <li>Restore scope</li>
     *  <li>Visit condition expression</li>
     *  <li>If condition expression is not BOOL, complain</li>
     *  <li>Return null</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(RepeatNode n)
    {
        table = table.enterScope(n.body);
        n.body.accept(this);
        table = table.exitScope();
        Type expr = (Type) n.expr.accept(this);
        if (!Type.isBoolean(expr) && !Type.isUndef(expr))
        {
            ErrorHandler.complain("Expression in repeat statement must evaluate to boolean");
        }
        return null;
    }
    
    /**
     * Visits WhileNode
     * 
     * <ul>
     *  <li>Visit condition expression</li>
     *  <li>If condition expression is not BOOL, complain</li>
     *  <li>Enter scope of while body, visit while body</li>
     *  <li>Restore scope</li>
     *  <li>Return null</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(WhileNode n)
    {
        Type expr = (Type) n.expr.accept(this);
        if (!Type.isBoolean(expr) && !Type.isUndef(expr))
        {
            ErrorHandler.complain("Expression in while statement must evaluate to boolean");
        }
        table = table.enterScope(n.body);
        n.body.accept(this);
        table = table.exitScope();
        return null;
    }
    
    /**
     * Visits AssignNode.
     * 
     * Check to see that both sides of the assignment have valid types.
     * <ul>
     *  <li>Get the type of each side.</li>
     *  <li>Check that neither side is of type UNDEF.</li>
     *  <li>Check that both sides have the same type.</li>
     *  <ul>
     *      <li>If they differ in type, check to see if an int is being assigned to a float.</li>
     *      <li>If not complain that both sides of an assign must be of equal type</li>
     *      </ul>
     *   <li>Return null, as an assign does not have a type</li>
     * </ul>
     * 
     * @param n
     * @return
     */
    public Type visit(AssignNode n)
    {
        Type t1 = (Type) ((n.var!=null) ? n.var.accept(this) : null);
        Type t2 = (Type) ((n.expr!=null) ? n.expr.accept(this) : null);
        if (t1 == null || t2 == null || t1==Type.UNDEF || t2==Type.UNDEF)
            return null;
        if (t1 != t2)
        {
            if (t1 == Type.FLOAT && t2 == Type.INT);
            else ErrorHandler.complain("The two sides of an assignment must have matching types: " + t1.getType() + " = " + t2.getType());
        }
        return null;
    }

    /**
     * Visit StatementListNode
     *
     * <ul>
     *  <li>Visit the left child</li>
     *  <li>Recursively visit the right children<li/>
     *  <li>Return null, as StatementListNode does not have a type</li>
     * </ui>
     * 
     * @param n
     * @return
     */
    public Type visit(StatementListNode n)
    {
        n.left.accept(this);
        if (n.right != null)
        {
            n.right.accept(this);
        }
        return null;
    }
    
    /**
     * Visit BlockBodyNode
     *
     * <ul>
     *  <li>If it exists visit the declaration list</li>
     *  <li>If it exists visit the statement list<li/>
     *  <li>Return null, as BlockBodyNode does not have a type</li>
     * </ui>
     * 
     * @param n
     * @return
     */
    public Type visit(BlockBodyNode n)
    {
        if (n.decl != null)
        {
            n.decl.accept(this);
        }
        if (n.stm != null)
        {
            n.stm.accept(this);
        }
        return null;
    }
    
    /**
     * Visit DeclarationListNode
     *
     * <ul>
     *  <li>If it exists visit the left declaration</li>
     *  <li>If it exists recursively visit the right declaration list<li/>
     *  <li>Return null, as DeclarationListNode does not have a type</li>
     * </ui>
     * 
     * @param n
     * @return
     */
    public Type visit(DeclarationListNode n)
    {
        if (n.right != null)
        {
            n.right.accept(this);
        }
        if (n.left != null)
        {
            n.left.accept(this);
        }
        return null;
    }

    /*
     * Lists
     *
     */

    /*
     * Helper methods
     *
     */
    
    /**
     * Private helper method. Collects types of expression nodes
     * in a ExprListNode.
     *
     * <ul>
     *  <li>If n is null returns an empty List</li>
     *  <li>If n is not null returns a list of expressions</li>
     * </ul>
     *
     * @param n
     * @return
     */
    private List<Type> visitExprList(ExprNode n)
    {
        List<Type> expr = new ArrayList<Type>();
        for (ExprNode cur = n; cur!=null; cur = cur.next)
        {
            expr.add((Type) cur.accept(this));
        }
        return expr;
    }
}